Vòng loại của giải diễn ra từ 10 tháng 3 năm 2003 đến 8 tháng 10 năm 2005. Khác với những giải trước, giải này không có vòng sơ loại. Do đó vòng loại chia ra nhiều bảng hơn gồm 49 đội chia làm 5 bảng để chọn lấy 13 đội đầu bảng và đội thứ nhì có thành tích tốt nhất vào vòng chung kết cùng đương kim vô địch Cameroon và chủ nhà Tunisia. Vòng loại này cùng là vòng loại Giải vô địch bóng đá thế giới 2006.

Các đội tham dự